package offer.offer04;

import java.util.ArrayList;
import java.util.List;

/**
 * 8, 9……看看别人的写法吧……
 * 取模一下, 然后用ArrayList的remove?ArrayList的底层是什么?remove的复杂度?
 */
public class Solution62 {
    public int lastRemaining(int n, int m) {
        List<Integer> nList = new ArrayList<>();
        for(int i = 0; i < n; i++) nList.add(i);
        int preLoc = 0;
        int curLoc = 0;
        for(int i = 0; i < n - 1; i++){
            //因为是一个环, 所以可以这样找下一位在哪里;
            curLoc = (preLoc - 1 + m) % nList.size();
            nList.remove(curLoc);
            preLoc = curLoc;
        }
        return nList.get(0);
    }

    //约瑟夫环是有递推的
    public int lastRemaining2(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution62().lastRemaining(10, 17));
    }
}
